#include<bits/stdc++.h>
#define sd(n) scanf("%d",&n) 
#define sld(n) scanf("%lld",&n)
#define pd(n) printf("%d", (n))
#define pld(n) printf("%lld", n)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fi first
#define se second
const int N=2e5;
const int maxn=1e6;
#define INF 0x7fffffff
typedef long long int ll;
using namespace std;
//----------------------------------------------------------------------------//
int a[N+10];
//pair<int,int> b[N+10];//每对朋友
int b[N+10][2];
int c[N+10];//记录每个人出现的次数
//每个不被邀请的人有一个不开心值,被邀请的人中如果有两个人互为朋友,则蛋糕数+1
//要求蛋糕数为偶数的同时保证最小值
void solve()
{
    int n,m;
    sd(n);sd(m);

    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++)
    {
        cin>>b[i][0]>>b[i][1];
        c[b[i][0]]++;
        c[b[i][1]]++;
    }
    if(m%2==0)//m为偶数直接输出
    {
        pd(0);
        puts("");
        return;
    }

    int ans=1000000000;//m为奇数,删除一个人(这人有奇数个朋友),删除两个人(两人都有偶数个朋友,且两者互为朋友)
    for(int i=1;i<=n;i++)
    {
        if(c[i]%2!=0)
            ans=min(ans,a[i]);
    }
    for(int i=1;i<=m;i++)
    {
        if(c[b[i][0]]%2==0&&c[b[i][1]]%2==0)
            ans=min(ans,a[b[i][0]]+a[b[i][1]]);
    }
    cout<<ans;
    puts("");


}

int main()
{
    int T;
    sd(T);
    while (T--)
    {
        solve();
    }
    return 0;
}